// https://www.lintcode.com/problem/minimum-depth-of-binary-tree/

/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */

public class Solution {
    /**
     * @param root: The root of binary tree
     * @return: An integer
     */
    public int minDepth(TreeNode root) {
        // write your code here
        ret = 2147483647;
        if (null == root) {
            return 0;
        }
        _minDepth(root, 1);
        return ret;
    }
    
    private void _minDepth(TreeNode node, int depth) {
        if (!((node.left != null) || (node.right != null))) {
            // 叶子节点
            if (depth < ret) {
                ret = depth;
            }
        }
        else {
            if (node.left != null) {
                _minDepth(node.left, depth + 1);
            }
            if (node.right != null) {
                _minDepth(node.right, depth + 1);
            }
        }
    }
    
    private int ret;
}